{\magonebf 3.10 Partitions (partition)}

An instance of the data type $partition$ consists of a finite set of 
items (predefined type $partition\_item$) and a partition of this set 
into blocks.


\def\name{$partition$}
\def\type{partition}

\bigskip
{\bf 1. Creation of a partition}


\create P {}

Creates an instance $P$ of type $partition$ and initializes it to the empty 
partition. 



\bigskip
{\bf 2. \operations}

\+\cleartabs & \hskip 3.2truecm & \hskip 4.8truecm &\cr
\+\op partition\_item make\_block {}
                             {returns a new $partition\_item$ $it$ and adds}
\+\nop                       {the block $\{it\}$ to partition $P$.}
\smallskip
\+\op partition\_item find {partition\_item\ p} {}
\+\nop                      {returns a canonical item of the block that}
\+\nop                      {contains item $p$, i.e., if $P$.same\_block($p,q$)}
\+\nop                      {then $P$.find($p$) = $P$.find($q$).}
\+\nop                      {\precond{$p$ is an item in $P$.}}
\smallskip
\+\op bool            same\_block {partition\_item\  p,\ partition\_item\ q} {}
\+\nop                       {returns true if $p$ and $q$ belong to the same}
\+\nop                       {block of partition $P$.}
\+\nop                       {\precond{$p$ and $q$ are items in $P$.}}
\smallskip
\+\op void            union\_blocks {partition\_item\ p,\ partition\_item\ q} {}
\+\nop                       {unites the blocks of partition $P$ containing}
\+\nop                       {items $p$ and $q$.}
\+\nop                       {\precond{$p$ and $q$ are items in $P$.}}


\bigskip
{\bf 3. Implementation}

Partitions are implemented by the union find algorithm with weighted union
and path compression (cf. [T83]).  Any sequence of $n$ make\_block and 
$m \ge n$ other operations takes time $O(m\alpha(m,n))$, where $\alpha$ is 
a functional inverse of Ackerman's function.



\bigskip
{\bf 4. Example }

Spanning Tree Algorithms (cf. graph)
